package vip.zhenzicheng.algorithm.leetcode;

import java.util.HashMap;
import java.util.Map;

/**
 * <a href="https://leetcode.cn/problems/climbing-stairs/">爬楼梯</a>
 * 假设你正在爬楼梯，需要 n 阶才能到楼顶，每次能爬 1 或 2 个台阶。
 * 一共有多少种不同的方法可以爬到楼顶？ 1<=n<=45
 * input:[n=2],output:[2] -> 1+1 / 2
 * input:[n=3],output:[3] -> 1+1+1 / 1+2 / 2+1
 *
 * @author zhenzicheng
 * @date: 2022-05-30 20:59
 */
public class ClimbingStairs_70 {

  /**
   * 第一种解法直接使用递归，但是时间复杂度较高并且存在重复计算过程
   * O(n^2) 超时
   */
  // public int climbStairs(int n) {
  //   if (n == 1) {
  //     return 1;
  //   }
  //   if (n == 2) {
  //     return 2;
  //   }
  //
  //   return climbStairs(n - 1) + climbStairs(n - 2);
  // }

  private Map<Integer, Integer> storeMap = new HashMap<>();

  /**
   * 相当于二叉树从下往上递归求到 f(n) = f(n-1) + f(n-2)
   */
  // public int climbStairs(int n) {
  //   if (n == 1) {
  //     return 1;
  //   }
  //   if (n == 2) {
  //     return 2;
  //   }
  //
  //   if (storeMap.get(n) != null) {
  //     return storeMap.get(n);
  //   }else {
  //     int result = climbStairs(n - 1) + climbStairs(n - 2);
  //     storeMap.put(n, result);
  //     return result;
  //   }
  // }


  /**
   * 第一种解法直接使用递归，但是时间复杂度较高并且存在重复计算过程
   */
  public int climbStairs(int n) {
    if (n == 1) {
      return 1;
    }
    if (n == 2) {
      return 2;
    }

    int result = 0;
    // 从3开始
    for (int i = 3, pre = 2, prePre = 1; i <= n; i++) {
      result = prePre + pre;
      prePre = pre; // 要原来两个数中大的那个
      pre = result; // 保存原来两个数和即最大的那一个
    }

    return result;
  }
}
